5582

Created at : 2024-05-11 21:39
5582

#include <iostream>
#define MAXLEN 4000

using namespace std;

int main()
{
    string A, B;
    cin >> A >> B;

    int Length = 0;
    int p[MAXLEN + 1][MAXLEN + 1] = { 0 };
    int N = A.length(), M = B.length();
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j <= M; ++j)
        {
            if(A[i - 1] == B[j - 1])
            {
                p[i][j] = p[i - 1][j - 1] + 1;
                Length = max(Length, p[i][j]);
            }
        }
    }    

    cout << Length;

    return 0;
}

ABRA와 ABRC두 문자열을 아래와 같이 테이블을 만들어 보자. 일단 완성된 테이블을 보자.

	A	B	R	A
A	1			1
B		2
R			3
C
위와 같이 표현되었을때 알 수 있는 것은 대각선방향으로 연속으로 일치하는 경우, 즉 A[i] == B[j]이고 A[i + 1] == B[j + 1]인 경우 부분 문자열이 완성된다. 이 점을 이용해서 테이블을 완성시키며 가장 긴 길이를 갱신시켜주면 된다.
코드는 아래와 같다.

유형